package com.example.interview.Tree;



public class LowestCommonAncestor {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果根节点为空，直接返回null
        if (root == null) return null;
        
        // 如果根节点是其中一个目标节点，直接返回根节点
        if (root == p || root == q) return root;
        
        // 在左子树中查找p和q的最近公共祖先
        TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
        // 在右子树中查找p和q的最近公共祖先
        TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);
        
        // 如果左右子树分别找到了p和q，则当前节点是最近公共祖先
        if (leftLCA != null && rightLCA != null) {
            return root;
        }
        
        // 如果只有一边找到了最近公共祖先，则返回那个节点
        return (leftLCA != null) ? leftLCA : rightLCA;
    }

    public static void main(String[] args) {
        // 创建示例二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);

        LowestCommonAncestor solution = new LowestCommonAncestor();
        TreeNode p = root.left.left;
        TreeNode q = root.left.right.left;
        TreeNode lca = solution.lowestCommonAncestor(root, p, q);
        
        System.out.println("Lowest Common Ancestor of " + p.val + " and " + q.val + " is: " + lca.val);
    }
}
